package com.str.BT;
public class Traversal {

  public static void insert(BTNode ref, Object val) {
    if (ref == null) return;
    if ((int)(Math.random()*2) == 0)
      if (ref.left == null)
        ref.left = new BTNode(val);
      else 
        insert(ref.left, val);
    else 
      if (ref.right == null)
        ref.right = new BTNode(val);
      else
        insert(ref.right, val);
  }

  public static void print(BTNode ref, int level) {
    if (ref == null) return;
    print(ref.right, level+1);
    for (int i=0; i<level; i++)
      System.out.print("    ");
    System.out.println(ref.data);
    print(ref.left, level+1);
  }

  public static void preOrder(BTNode ref) {
	if (ref == null) return;
	System.out.print(ref.data + " ");	
	preOrder(ref.left);
    preOrder(ref.right);
  }

  public static void inOrder(BTNode ref) {
	if (ref == null) return;
	inOrder(ref.left);
	System.out.print(ref.data + " ");
    inOrder(ref.right);
  }

  public static void postOrder(BTNode ref) {
	if (ref == null) return;
	postOrder(ref.left);	
    postOrder(ref.right);
    System.out.print(ref.data + " ");
  }

  public static void main(String[] args) {
  	final int numNodes = 10;
    BTNode root = new BTNode(new Character((char) ('A')));
    for (int i=1; i<numNodes; i++)
      Traversal.insert(root, new Character((char) ('A'+i)));
    Traversal.print(root, 0);
    
    System.out.print("\nPre-order:  ");    
    Traversal.preOrder(root);

    System.out.print("\nIn-order:   ");     
    Traversal.inOrder(root);
       
    System.out.print("\nPost-order: "); 
    Traversal.postOrder(root);
    System.out.println();    
  }
}
